package com.zsp.test.djs;

import java.util.*;

public class AStarAlgorithm {

    // A*算法实现
    public static List<String> aStar(Graph graph, String start, String goal, Map<String, Integer> heuristic) {
        // 优先队列用于存储待处理节点，按fCost升序排列
        PriorityQueue<AStarNode> openSet = new PriorityQueue<>(Comparator.comparingInt(AStarNode::getFCost));
        // 存储所有已访问节点
        Map<String, AStarNode> allNodes = new HashMap<>();

        // 初始化起始节点
        AStarNode startNode = new AStarNode(start, 0, heuristic.get(start), null);
        openSet.add(startNode);
        allNodes.put(start, startNode);

        // 主循环，处理所有待处理节点
        while (!openSet.isEmpty()) {
            // 从优先队列中取出fCost最小的节点
            AStarNode current = openSet.poll();

            // 如果当前节点是目标节点，返回路径
            if (current.name.equals(goal)) {
                return reconstructPath(current);
            }

            // 遍历当前节点的所有邻居节点
            for (Edge edge : graph.getEdges(current.name)) {
                int tentativeGCost = current.gCost + edge.weight; // 计算到邻居节点的gCost
                AStarNode neighborNode = allNodes.getOrDefault(edge.destination, new AStarNode(edge.destination, Integer.MAX_VALUE, heuristic.get(edge.destination), null));

                // 如果通过当前节点到达邻居节点的路径更短，更新邻居节点的信息
                if (tentativeGCost < neighborNode.gCost) {
                    neighborNode.gCost = tentativeGCost;
                    neighborNode.parent = current;

                    // 如果邻居节点不在待处理队列中，加入队列
                    if (!openSet.contains(neighborNode)) {
                        openSet.add(neighborNode);
                    }

                    // 更新或添加邻居节点到已访问节点集合
                    allNodes.put(edge.destination, neighborNode);
                }
            }
        }

        return Collections.emptyList(); // 如果没有找到路径，返回空列表
    }

    // 回溯路径，从目标节点回到起始节点
    private static List<String> reconstructPath(AStarNode node) {
        List<String> path = new ArrayList<>();
        while (node != null) {
            path.add(node.name);
            node = node.parent;
        }
        Collections.reverse(path); // 反转路径以得到从起始到目标的顺序
        return path;
    }

    public static void main(String[] args) {
        // 创建图并添加边
        Graph graph = new Graph();
        graph.addEdge("A", "B", 4);
        graph.addEdge("A", "C", 2);
        graph.addEdge("B", "C", 5);
        graph.addEdge("B", "D", 10);
        graph.addEdge("C", "D", 3);
        graph.addEdge("D", "E", 4);

        // 定义启发式函数（hCost）
        Map<String, Integer> heuristic = new HashMap<>();
        heuristic.put("A", 7);
        heuristic.put("B", 6);
        heuristic.put("C", 2);
        heuristic.put("D", 1);
        heuristic.put("E", 0);

        // 执行A*算法并输出结果
        List<String> path = aStar(graph, "A", "E", heuristic);
        System.out.println("A to E: 最短" + path);
    }
}
// 定义A*算法节点类
class AStarNode {
    String name; // 节点名称
    int gCost; // 从起始节点到当前节点的实际代价
    int hCost; // 从当前节点到目标节点的启发式估计代价
    AStarNode parent; // 当前节点的父节点，用于路径回溯

    // 构造函数
    public AStarNode(String name, int gCost, int hCost, AStarNode parent) {
        this.name = name;
        this.gCost = gCost;
        this.hCost = hCost;
        this.parent = parent;
    }

    // 获取节点的总代价（fCost = gCost + hCost）
    public int getFCost() {
        return gCost + hCost;
    }
}

class Graph {
    // 使用邻接表表示图
    private final Map<String, List<Edge>> adjList = new HashMap<>();

    // 添加边的方法
    public void addEdge(String source, String destination, int weight) {
        // 对于无向图，添加双向边
        adjList.computeIfAbsent(source, k -> new ArrayList<>()).add(new Edge(destination, weight));
        adjList.computeIfAbsent(destination, k -> new ArrayList<>()).add(new Edge(source, weight));
    }

    // 获取节点的邻居
    public List<Edge> getEdges(String node) {
        return adjList.getOrDefault(node, new ArrayList<>());
    }
}

// 边的类，包含目标节点和权重
class Edge {
    String destination;
    int weight;

    public Edge(String destination, int weight) {
        this.destination = destination;
        this.weight = weight;
    }
}
